package com.hyc.DataStructure.Stack;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Stack
 * @className: Calculator
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/24 20:39
 * @version: 1.0
 */
public class Calculator {
    public static void main(String[] args) {
        //  根据文章的思路 我们这里完成对一串计算只包含加减乘除的表达式运算操作
        String expression = "3+2*6-2";
        /** 计算思路 使用栈完成表达式的计算思路
         * 1.通过一个index值（素引）,来遍历我们的表达式
         * 2.如果我们发现是一个数字，就直接入数栈
         * 3.如果发现扫描到是一个符号，就分如下情况
         * 3.1如果发现当前的符号栈为空，就直接入栈
         * 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
         * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
         * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
         * 于栈中的操作符，就直接入符号找。
         * 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
         * 5.最后在数栈只有一个数字，就是表达式的结果
         * 验证：3+2*6-2=13
         * 这里我们就根据上面的思路实现接下来的思路
         * */
        // 创建两个栈 一个存放需要计算的数字 一个存放需要运算的符号
        ArrayCalStack numStack = new ArrayCalStack(10);
        ArrayCalStack operStack = new ArrayCalStack(10);
        //    定义相关变量
        int index = 0; //用于指针扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        //将每次扫描得到的char保存到ch
        char ch;
        //用于萍姐多位数
        String keepNums = "";
        //开始while 循环扫描表达式 expression
        while (true) {
            //    一次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //    判断ch 是什么（数字或者符号）之后进行操作
            if (operStack.isOper(ch)) {
                /*   如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
                 * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
                 * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
                 * 于栈中的操作符，就直接入符号找。*/
                //非空判断
                if (!operStack.isempty()) {
                    if (operStack.priotrity(ch) <= operStack.priotrity(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        //    把运算结果压入 数字栈
                        numStack.push(res);
                        // 之后将当前的符号压入栈 不然会缺失一个运算符号
                        operStack.push(ch);
                    } else {
                        //如果当前的操作符的优先级别大于栈中的操作符 就直接进入符号栈
                        operStack.push(ch);
                    }
                } else {
                    //    如果为空直接入符号栈
                    operStack.push(ch);
                }
            } else {
                //  如果是数字 就直接进入数字栈
                /*思路
                 * 这里我们要考虑到多位数 在处理多位数的时候
                 *  我们需要扫描这个数的下一位一直到找到下一个符号
                 * 这个时候我们定义一个字符串用于拼接找到的数
                 * */
                //    处理多位数
                keepNums += ch;
                //    如果ch已经是 expression 最后一位name就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNums));
                } else {
                    //    判断下一个字符是不是数字 ，如果是就继续向下判断 是运算符则入栈，这里我们要看的是结束的地方是不是符号
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        //如果最后一位事原酸父则如入栈 这里我们的操作变化就是 keepnums =1 或者是 keepnums = 123
                        numStack.push(Integer.parseInt(keepNums));
                        //    加入之后能讲 keepnunms清空 用于下一位的判断
                        keepNums = "";
                    }
                }
            }
            //    让 index +1 并判断是否扫描到expression 最后
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        //    当表达式扫描完毕，就循序的从数栈和符号栈中 pop出相应的数和符号，并且运行
        while (true) {
            //    如果符号为空，则计算到最后的结果，数栈中只有一个数字【结果】
            if (operStack.isempty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            //入栈
            numStack.push(res);
        }
        //    将数栈最后的数，pop出，就是结果
        int res2 = numStack.pop();
        System.out.printf("表达式%s = %d", expression, res2);
    }
}


/*
 *  应为要实现计算器 我们需要编写一些新的功能，
 * */
class ArrayCalStack {
    //栈的最大长度
    private int MaxSize;
    //模拟栈 数据就放在这个数组里
    private int[] stack;
    // 等于栈顶 默认等于-1 代表最底部分
    private int top = -1;

    public ArrayCalStack() {

    }

    // 初始化栈
    public ArrayCalStack(int maxSize) {
        MaxSize = maxSize;
        stack = new int[maxSize];
    }

    //返回栈顶 只是显示 并不是 pop 不会改变栈的结构
    public int peek() {
        return stack[top];
    }

    //判断栈是否是满的
    public boolean isFull() {
        return top == MaxSize - 1;
    }

    //判断栈 是否是空的
    public boolean isempty() {
        return top == -1;
    }

    //将数据压入栈
    public void push(int data) {
        if (isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = data;
    }

    //    将数据取出栈
    public int pop() {
        if (isempty()) {
            throw new RuntimeException("栈是空的 无法取出");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //遍历栈 遍历的时候需要从栈顶开始显示数据
    public void list() {
        if (isempty()) {
            System.out.println("栈是空的");
        }
        //   从栈顶开始输出 其实就是倒序的输出数组
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }


    /* 返回运算符的优先级 这个规则我们可以自己来设定 优先级使用数字来表示
     * 数字越大优先级约高
     * */
    public int priotrity(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;
        }
    }

    //    判断是不是一个字符
    public boolean isOper(char val) {
        return val == '*' || val == '/' || val == '+' || val == '-';
    }

    //    计算操作 用于执行运算
    public int cal(int num1, int num2, int oper) {
        // 存放计算的结果
        int res = 0;
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '/':
                res = num2 / num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            default:
                break;

        }
        return res;
    }
}